昨天寫到 two number sum 的兩種解法，一種使用兩層迴圈，時間為 O(n^2)；另一種使用 hash table，時間為 O(n)。這裡先寫第三種解法，時間表現雖然介於前兩者之間，但很簡潔好懂，也很適合延伸用來解 three number sum 問題。

這個解法是利用有序陣列的特性加上指標 (pointers) 來解題。
例如輸入為 [3, 5, -4, 8, 11, 1, -1, 6], 10
步驟：

1. 將陣列排序，得到 [-4, -1, 1, 3, 5, 6, 8, 11]。
2. 以兩個指標 (left, right) 分別指向最小和最大的數字，將兩數字相加後與目標數字相比。
   [-4, -1, 1, 3, 5, 6, 8, 11]
     ^              ^
   left           right
3. 若兩數和等於目標，也就是找到解，直接回傳指標指向的兩個數字。
4. 若兩數和小於目標，則將左邊指標往右移。
   例如目前 (-4 + 11) < 10，因為有序陣列，此時如果移動右邊的指標，兩數和只會變得更小，離目標更遠，所以將左邊指標右移。
5. 若兩數和大於目標，則將右邊指標往左移。
6. 在兩個指標不重疊的情況下，重複步驟 3-5，否則回傳空陣列。

n 為陣列長度
time: O(nlog(n)) 這個時間是因排序而來 (取正常發揮的排序演算法時間)，排序後只有進行常數時間運算所以忽略掉。
space: O(1)

function twoNumberSum(array, target) {
  array.sort((a, b) => a - b);
  let left = 0;
  let right = array.length - 1;
  while (left < right) {
    const sum = array[left] + array[right];
    if (sum === target) {
      return [array[left], array[right]];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return [];
}

以上面的解法為基礎，接著看 three number sum 問題。

problem

輸入為一陣列及一整數 target，如果陣列中有三個數字相加等於 target，以雙層陣列 (two-dimentional array) 的結構回傳所有數組，且所有數組要從小到大排序，否則回傳空陣列。
可以預設輸入陣列不為空陣列，且元素不重複。

sample input:
array = [12, 3, 1, 2, -6, 5, -8, 6]
target = 0

sample output:
[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

延續上一題的解法，稍微複雜一點，除了排序、指標外還用到迴圈。
步驟：

1. 以上方 sample input 為例，先將陣列排序，得到 [-8, -6, 1, 2, 3, 5, 6, 12]。
2. 以迴圈遍歷陣列。看每個數字 i 時，都以兩個指標 (left, right)，分別指向 i 後面一個數字，以及陣列最後一個數字。將三個數字和與目標數字做比較。
3. 若三個數字和等於目標，代表找到一組解，記錄下來，同時移動兩個指標。
4. 若三個數字和小於目標，將左邊指標往右移。
5. 若三個數字和大於目標，將右邊指標往左移。
6. 兩個指標不重疊的情況，每次進入迴圈重複步驟 3-5。迴圈結束後回傳結果陣列。

值得注意的是，不同於 two number sum 一找到解就可以回傳結果，這題可能有不只一組解，因此也多了找到解後，需要同時將指標都向內移動的這種情況。

n 為陣列長度
time: O(n^2) 迴圈 + 每次迴圈又用指標看過所有數字一次。
space: O(n) 輸出陣列可能會放入 n 個數字。

function threeNumberSum(array, target) {
  array.sort((a, b) => a - b);
  const results = [];
  // 迴圈只到倒數第三位，後面留兩個位置給指標
  for (let i = 0; i < array.length - 2; i++) {
    let left = i + 1;
    let right = array.length - 1;
    while (left < right) {
      const sum = array[i] + array[left] + array[right];
      if (sum === target) {
        results.push([array[i], array[left], array[right]]);
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      }
    }
  }
  return results;
}

如果從 three number sum 再進階到 four number sum，一切就會變得更複雜，希望...完賽前有機會整理成筆記，明天先寫其他的陣列題目。